/*
Date:20210411 20:56pm
key:用set记录节点 将当前节点放入组合 V 去掉记录 退出组合
*/

class Solution {
public:
    //这里改成引用快了三个样例
    // int sum_of_V(vector<int>&V)
    // {
    //     return V[0]+V[1]+V[2];
    // }

    void F(vector<int> nums,int x,set<int>&S,vector<int>&V,set<vector<int>>&Big_S)
    {
        //搜索终止条件，V.size()==3
        if(V.size()==3)
        {
            if(V[0]+V[1]+V[2]==0)
            {
                // for(auto j:V)
                // {
                //     cout<<j<<" ";
                // }
                // cout<<"\n";
                //收集结果前要sort，是组合问题，三元组内部排序不同的都当做同一个。
                vector<int> V3=V;
                sort(V3.begin(),V3.end());
                Big_S.insert(V3);
                
            }
            //否则什么也不做
        }
        else
        {
            //特别注意，原vector有重复元素，因此放进set里的最好是下标。一定不能是元素。
            //除去x和之前元素，对剩下的元素遍历递归
            for(int i=0;i<nums.size();i++)
            {
                //遍历前放入set，引用放入，免得又递归回自己
                if(S.count(i)==0)
                {
                    // cout<<S.count(6)<<"S.count(6) "<<S.count(6);
                    V.push_back(nums[i]);
                    S.insert(i);
                    
                    F(nums,nums[i],S,V,Big_S);
                    // cout<<S.count(6)<<" ";
                    S.erase(i);
                    V.pop_back();
                }
            }
        }

    }
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        vector<vector<int>>Big_V;
        //特殊情况
        if(nums.size()<=2)
        {
            return Big_V;
        }
        set<int>S1;
        set<int>S;
        vector<int>V;
        //遍历过程中用set收集，否则怎么去重
        set<vector<int>>Big_S;
        for(int i=0;i<nums.size();i++)
        {
            //重复元素不要遍历
            if(S1.empty()||S1.count(nums[i])==0)
            {
                V.push_back(nums[i]);
                S.insert(i);
                F(nums,nums[i],S,V,Big_S);
                V.pop_back();
                S1.insert(nums[i]);
                //以当前nums[i]为起点的排列都检查过了，因此后面的任何组合都不会有nums[i]在里面
                //S.erase(i);
                
            }
            
        }
        for(auto j:Big_S)
        {
            Big_V.push_back(j);
        }
    return Big_V;
    }
};